#include <stdio.h>
#include <stdlib.h>
#include "strings.h"
#include <algorithm>
#include <deque>
#define DEFAULT_MAX_PRICE 65536
#define DEFAULT_MAX_ORDERS 1000000
#define NO_ORDER_ID -1

typedef unsigned long TOrderID;
typedef long TPrice;
typedef size_t TSize;
typedef enum {
	BUY = 0,
	SELL
} TSide;
typedef char TSymbol[10];

class TOrder {
public:
	TSymbol sym;
	TOrderID oid;
	TSize qty;
	TPrice px;
	TOrder* next;
	TSide side;
};

class TPriceLevel {
public:
	TOrder* headOrder;
	TOrder* tailOrder;
	TSize qty;
};

template <long MAX_ORDERS = DEFAULT_MAX_ORDERS, long MAX_PRICE = DEFAULT_MAX_PRICE>
class TOrderBook {
protected:
	TPriceLevel priceLevels[MAX_PRICE + 1]; // 0th index is always unused, prices start from 1
	TPrice minSell, maxBuy;
	TOrder orders[MAX_ORDERS]; //order container
	TOrderID nextOID;

	TOrderID addOrder(TOrder& order) {
		order.oid = nextOID++;
		TPriceLevel& priceLevel = priceLevels[order.px];
		if (priceLevel.headOrder == NULL)
			priceLevel.headOrder = priceLevel.tailOrder = &order;
		else {
			priceLevel.tailOrder->next = &order;
			order.next = NULL;
		}

		if (order.side == BUY && order.px > maxBuy)
			maxBuy = order.px;
		if (order.side == SELL && order.px < minSell)
			minSell = order.px;

		priceLevel.qty += order.qty;
		return order.oid;
	}

	void reportCross(const TOrderID& id, const TOrderID& id2, const TSize& qty, const TPrice& px) {

	}

	TOrderID executeBuyOrder(TOrder& order) {
		TOrder* askOrder;
		do {
			TPriceLevel& priceLevel = priceLevels[minSell];
			while ((askOrder = priceLevel.headOrder) != NULL) {
				TSize crossQty = std::min(order.qty, askOrder->qty);
				reportCross(order.oid, askOrder->oid, crossQty, minSell);
				order.qty -= crossQty;
				askOrder->qty -= crossQty;
				priceLevel.qty -= crossQty;
				if (askOrder->qty == 0) {
					priceLevel.headOrder = priceLevel.headOrder->next;
				}
				if (order.qty == 0) {
					return NO_ORDER_ID; // we have completed the execution of the order
				}
			}
			priceLevel = priceLevels[++minSell];
		} while (order.px >= minSell);
		return addOrder(order);
	}

	TOrderID executeSellOrder(TOrder& order) {
		TOrder* buyOrder;
		do {
			TPriceLevel& priceLevel = priceLevels[maxBuy];
			while ((buyOrder = priceLevel.headOrder) != NULL) {
				TSize crossQty = std::min(order.qty, buyOrder->qty);
				reportCross(order.oid, buyOrder->oid, crossQty, maxBuy);
				order.qty -= crossQty;
				buyOrder->qty -= crossQty;
				priceLevel.qty -= crossQty;

				if (buyOrder->qty == 0) {
					priceLevel.headOrder = priceLevel.headOrder->next;
				}
				if (order.qty == 0) {
					if (priceLevel.headOrder == NULL)

					return NO_ORDER_ID; // we have completed the execution of the order
				}
			}
			priceLevel = priceLevels[--maxBuy];
		} while (order.px <= maxBuy);
		return addOrder(order);
	}

public:
	TOrderBook() {
		bzero(&priceLevels, sizeof(TPriceLevel) * (MAX_PRICE + 1));
		bzero(&orders, sizeof(TOrder) * MAX_ORDERS);
		nextOID = maxBuy = 0; // no order in the book
		minSell = MAX_PRICE;
	}

	TOrderID processOrder(TOrder& order) {
		switch (order.side) {
		case BUY:
			if (order.px >= minSell) {
				return executeBuyOrder(order);
			} else {
				return addOrder(order);
			}
			break;
		case SELL:
			if (order.px <= maxBuy) {
				return executeSellOrder(order);
			} else {
				return addOrder(order);
			}
			break;
		}
		return NO_ORDER_ID;
	}

	void cancelOrder(const TOrderID& id) {

	}
};

int main(void) {
	TOrderBook<> ob;
	return EXIT_SUCCESS;
}
